package com.sx.sx1.lintcode.day717;

import java.util.*;

public class LC1783_LC1577 {

    static class TreeNode {
        public int val;
        public TreeNode left, right;

        public TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }

    static class Solution {
        /**
         * @param root: A Tree
         * @return: Postorder in ArrayList which contains node values.
         */
        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> ans = new ArrayList<>();
            Stack<TreeNode> s1 = new Stack<>();
            Stack<TreeNode> s2 = new Stack<>();

            if (root != null) {
                s1.add(root);
            }

            while (!s1.isEmpty()) {
                TreeNode pop = s1.pop();
                s2.add(pop);
                if (pop.left != null) {
                    s1.add(pop.left);
                }

                if (pop.right != null) {
                    s1.add(pop.right);
                }
            }

            while (!s2.isEmpty()) {
                ans.add(s2.pop().val);
            }
            return ans;
        }
    }


    static class Solution1577 {
        /**
         * @param root:
         * @return: the sum of leafnode
         */
        public int sumLeafNode(TreeNode root) {
            Queue<TreeNode> q = new LinkedList<>();
            q.add(root);
            int ans =0;
            while (!q.isEmpty()){
                int size = q.size();
                for (int i = 0; i <size ; i++) {
                    TreeNode pop = q.poll();
                    if(pop.left ==null && pop.right ==null){
                        ans+= pop.val;
                    }
                    if(pop.left!=null){
                        q.add(pop.left);
                    }

                    if(pop.right!=null){
                        q.add(pop.right);
                    }
                }
            }
            return ans;
        }
    }


}


/*
LintCode-Logo
学习
刷题
内推
VIP
其他...
搜索题目、标签、题集
邀请有礼
中文
avatar
您有211条未读消息，请及时查看
1783 · 二叉树的后序遍历
算法
简单
通过率
73%

题目
题解18
笔记
讨论27
排名
记录
描述
给出一棵二叉树，返回其节点值的后序遍历。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


首个数据为根节点，后面接着是其左儿子和右儿子节点值，"#"表示不存在该子节点。

样例
样例 1:

输入:{1,2,3}
输出:[2,3,1]

解释:
  1
 / \
2  3
样例 2:

输入:{1,2,#,3,4}
输出:[3,4,2,1]

解释:
    1
   /
  2
 / \
3  4
挑战
你能使用非递归实现么？

相关知识
学习《算法入门：递归》课程中的4.4二叉树的遍历 (代码讲解)相关内容 ，了解更多相关知识！
标签
相关题目

66
二叉树的前序遍历
简单
推荐课程

系统设计 System Design 2024版
数据库、API、GFS、视频流等16大系统设计详解，实战练习拿下面试/晋升“拦路虎”
17/133
已开启智能提示
发起考试
15 分 00 秒
123456789101112131415161718192021
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }

控制台
历史提交

 */

/*
LintCode-Logo
学习
刷题
内推
VIP
其他...
搜索题目、标签、题集
邀请有礼
中文
avatar
您有211条未读消息，请及时查看
1577 · 叶子节点的和
算法
中等
通过率
75%

题目
题解17
笔记
讨论24
排名
记录
描述
给个一颗二叉树，求出所有叶节点的和。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


样例
样例1:

输入:
{1,2,3,4,5}
输出: 12

解释：
      1
     / \
   2   3
  / \
4   5
叶子节点即为没有孩子结点的节点，4+5+3 = 12
样例2：

输入：
{12,3,7,4,5,#,#,2}
输出：14

解释：
      12
      / \
    3   7
   / \
 4   5
 /
 2
2+5+7 = 14
挑战
使用普通的深度或宽度优先遍历固然可行，但你能使用
𝑂
(
1
)
O(1) 的空间完成这道题目吗？

查看提示
标签
企业
Google
Amazon
推荐课程

ACM金牌逐行带刷班
最适合懒人的刷题课--躺平看算法大神在线coding，讲解思路+现场debug，手撕面试高频题
23/133
已开启智能提示
发起考试
30 分 00 秒
123456789101112131415161718192021
}
控制台
历史提交

 */